package com.day1.hw;

public class ArrayOperator {

	int[] A;

	public void swap(int i,int j){
		int temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	}
	private int partition(int l, int h,int pV,String... order){

		int low=l;
		int mid=l;
		int high=h;

		int orderr=1;
		if(order.equals("ascend"))
			orderr=-1;
		while(mid<=high){
			if(A[mid]==pV)
				mid++;
			else if(orderr*A[mid]<orderr*pV){
				swap(low,mid);
				low++;mid++;
			}
			else{
				swap(high,mid);
				high--;
			}
		}
		return low;
	}
	private void shiftMinusOnebyOverwrite(){
		int j=0;
		int i=0;
		while(i<A.length || j<A.length/2){
			if(A[i]!=-1)
			{
				A[j]=A[i];
				j++;
				i++;
			}
			else{
				i++;
			}
		}
		while(j<A.length)
		{
			A[j]=-1;
			j++;
		}
	}
	
	private void shiftMinusOnebySwap(){
		int i=0;
		int j=0;
		while(A[j]!=-1)
			j++;
		i=j;
		outerloop:
		while(i<A.length){
			while(A[i]==-1){
				i++;
				if(i==A.length)
					break outerloop;
			}
			swap(i,j);
			j=j+1;
		}
	}
	/*
	a is 2N and b is N
	for partition method, pass "ascend" as 4th param (optional) if ascending 
	order required, default=descending
	 */
	public void merge(int[] a, int[] b){
		
		A=a;
		//shiftMinusOnebySwap();
		shiftMinusOnebyOverwrite();
		//partition(0,A.length-1,-1);//cannot use partition as it is not ordered.
		
		//generate merged array
		int pb=b.length-1; //points to end of b 
		int pa=b.length-1;//points to middle of a
		int i=a.length-1;
		while(pa>=0  && pb>=0){
			if(A[pa]>b[pb]){
				swap(pa,i);
				i--;
				pa--;
			}
			else{
				A[i]=b[pb];
				pb--;
				i--;
			}
		}
		while(pb>=0)
		{
			A[pb]=b[pb];
			pb--;
		}
		
	}
	

}
